﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;

namespace TextEditApp.Algorithm
{
    /// <summary>
    /// 存放各种工具函数
    /// </summary>
    class Util
    {
        /// <summary>
        /// 传入一个文本，将其分割成字符串数组
        /// </summary>
        /// <param name="text"></param>
        /// <returns></returns>
        static public string[] GetWordArray(string text)
        {
            string pattern = @"[^a-zA-Z]";
            string[] words = Regex.Split(text, pattern);
            return words;
        }

        /// <summary>
        /// 用Sunday算法实现字符串匹配
        /// </summary>
        /// <param name="haystack">目标字符串</param>
        /// <param name="pattern">模式串</param>
        /// <returns></returns>
        static public int IndexOfSunday(string haystackRaw,string pattern,int off)
        {
            string haystack = haystackRaw.Substring(off);
            //Console.WriteLine(object.ReferenceEquals(haystack, haystackRaw));
            if (pattern.Length > haystack.Length) return -1;
            if (pattern=="") return off;
            //计算偏移表
            Hashtable offsetTable = new Hashtable();
            int index = 0;
            for(int i = 0;i < pattern.Length; i++)
            {
                if (!offsetTable.ContainsKey(pattern[i])) offsetTable.Add(pattern[i], pattern.Length - i);
                else offsetTable[pattern[i]] = pattern.Length - i;
            }

            while(index + pattern.Length <= haystack.Length)
            {
                bool flag = true;
                for(int i = 0;i < pattern.Length; i++)
                {
                    if(pattern[i] != haystack[index + i])
                    {
                        flag = false;
                        break;
                    }
                }

                if (flag) return index + off;
                if (index + pattern.Length >= haystack.Length) return -1;
                if (offsetTable.ContainsKey(haystack[index + pattern.Length])) index += (int)offsetTable[haystack[index + pattern.Length]];
                else index += pattern.Length + 1;
            }

            return -1;
        }


        public static int ExecuteKMP(string source, string pattern)
        {
            int[] next = Next(pattern);
            int i = 0;  //主串指针
            int j = 0;  //模式串指针
            //如果子串没有匹配完毕并且主串没有搜索完成
            while (j < pattern.Length && i < source.Length)
            {
                if (source[i] == pattern[j])    //i和j的逻辑意义体现于此，用于指示本轮迭代中要判断是否相等的主串字符和模式串字符
                {
                    i++;
                    j++;
                }
                else
                {
                    j = next[j];    //依照指示迭代回溯
                    if (j == -1)    //回溯有情况，这是第二种
                    {
                        i++;
                        j++;
                    }
                }
            }
            //如果j==pattern.Length则表示循环的退出是由于子串已经匹配完毕而不是主串用尽
            return j < pattern.Length ? -1 : i - j;
        }

        public static int[] Next(string pattern)
        {
            int[] next = new int[pattern.Length];
            next[0] = -1;
            if (pattern.Length < 2) //如果只有1个元素不用kmp效率会好一些
            {
                return next;
            }

            next[1] = 0;    //第二个元素的回溯函数值必然是0，可以证明：
            //1的前置序列集为{空集,L[0]}，L[0]的长度不小于1，所以淘汰，空集的长度为0，故回溯函数值为0
            int i = 2;  //正被计算next值的字符的索引
            int j = 0;  //计算next值所需要的中间变量，每一轮迭代初始时j总为next[i-1]
            while (i < pattern.Length)    //很明显当i==pattern.Length时所有字符的next值都已计算完毕，任务已经完成
            { //状态点
                if (pattern[i - 1] == pattern[j])   //首先必须记住在本函数实现中，迭代计算next值是从第三个元素开始的
                {   //如果L[i-1]等于L[j]，那么next[i] = j + 1
                    next[i++] = ++j;
                }
                else
                {   //如果不相等则检查next[i]的下一个可能值----next[j]
                    j = next[j];
                    if (j == -1)    //如果j == -1则表示next[i]的值是1
                    {   //可以把这一部分提取出来与外层判断合并
                        //书上的kmp代码很难理解的一个原因就是已经被优化，从而遮蔽了其实际逻辑
                        next[i++] = ++j;
                    }
                }
            }
            return next;
        }
        static public int IndexOfKMP(string haystack, string pattern, int off)
        {
            haystack = haystack.Substring(off);
            if (pattern.Length > haystack.Length) return -1;
            if (pattern == "") return off;
            int index = ExecuteKMP(haystack, pattern);

            for (int i = 0; i < pattern.Length; i++)
            {
                if (index == -1)     //因为考虑到kmp可能返回-1的情况，出现过数组越界
                    return -1;
                if (pattern[i] != haystack[index + i] )  
                    return -1;
            }
            return index + off;

        }

        //BM算法
        public static int Arithmetic_BM(string operateStr, string findStr)
        {
            //i：匹配开始的索引，j：operateStr字符串的索引迭代，k：findStr字符串索引迭代
            int i = 0, j = findStr.Length - 1, k = j;
            int n, m = 0; //n:坏字符规则计算出的移动位数，m:好后缀计算出的移动位数

            while (k >= 0 && j < operateStr.Length)
            {
                if (k == 0) //全部匹配，return
                {
                    return i;
                    break;
                }
                if (operateStr[j] == findStr[k]) //匹配，next
                {
                    j--;
                    k--;
                }
                else
                {
                    //当k<要匹配的字符串长度时，说明已经有匹配的字符了，即有“好后缀”
                    if (k < findStr.Length - 1)
                    {
                        //采用"好后缀规则"，先找出“全好后缀”有没有在前面存在
                        var goodSuffix = findStr.Substring(k + 1); //分割出全好后缀
                        var tempStr = findStr.Substring(0, k + 1); //去掉好缀后的字符串
                        //最全好后缀在剩下的字符串中出现
                        if (tempStr.Contains(goodSuffix))
                        {
                            var lastGoodSuffix = char.Parse(goodSuffix.Substring(goodSuffix.Length - 1)); //好后缀的最后一个字符
                            //找出 该字符的出现位置
                            IList<int> indexs = new List<int>();
                            for (int x = 0; x < tempStr.Length; x++)
                            {
                                if (lastGoodSuffix == tempStr[x])
                                {
                                    indexs.Add(x);
                                }
                            }
                            //找出 好后缀在搜索词中的上一次出现位置
                            var result = -1;
                            for (int x = indexs.Count - 1; x >= 0; x--)
                            {
                                if (indexs[x] >= goodSuffix.Length &&
                                    tempStr.Substring(indexs[x] - goodSuffix.Length + 1, goodSuffix.Length) == goodSuffix)
                                {
                                    result = indexs[x];
                                    break;
                                }
                            }
                            //好后缀规则结果
                            m = findStr.Length - 1 - result;
                        }
                        //最长好后缀没有没出现，但是好后缀最后一个字符，出现在头部
                        //后移位数 = 好后缀的位置 - (0)搜索词中的上一次出现位置
                        else if (findStr.Substring(0, 1) == findStr.Substring(findStr.Length - 1))
                        {
                            m = findStr.Length - 1;
                        }
                        else //好后缀只出现一次  (后移位数 = 好后缀的位置 - (-1)搜索词中的上一次出现位置)
                        {
                            m = findStr.Length;
                        }
                    }
                    //坏字符规则：后移位数 = 坏字符的位置 - 搜索词中的上一次出现位置
                    n = (j - i) - findStr.LastIndexOf(operateStr[j]);
                    //比较坏字符规则和好后缀规则移动的位数，得出最终移动位数
                    if (n > m)
                    {
                        i += n;
                        j = i + findStr.Length - 1;
                    }
                    else
                    {
                        i += m;
                        j = i + findStr.Length - 1;
                    }
                    k = findStr.Length - 1;
                    m = 0; //清零
                }
            }
            return -1;
        }

        static public int IndexOfBM(string haystack, string pattern, int off)
        {
            haystack = haystack.Substring(off);
            if (pattern.Length > haystack.Length) return -1;
            if (pattern == "") return off;
            //计算偏移表
            int index = Arithmetic_BM(haystack, pattern);
            for (int i = 0; i < pattern.Length; i++)
            {
                if (index == -1)     //因为考虑到kmp可能返回-1的情况，出现过数组越界
                    return -1;
                if (pattern[i] != haystack[index + i])
                    return -1;
            }
            return index + off;

        }

        //Horspool匹配算法，平均时间复杂度O(n)
        static public int HorspoolIndex(string source, string target, int pos)
        {
            int sLen = source.Length;
            int tLen = target.Length;
            int Ti = tLen - 1;      //目标字符串匹配位置
            int Si = pos + Ti;      //源字符串匹配位置

            if ((sLen - pos) < tLen)
                return -1;

            while ((Ti > -1) && (Si < sLen))
            {
                if (source[Si] == target[Ti])
                {
                    Ti--;
                    Si--;
                }
                else
                {
                    while ((Ti > -1) && (source[Si] != target[Ti]))
                    {
                        Ti--;
                    }
                    Si += tLen - 1 - Ti;
                    Ti = tLen - 1;
                }
            }

            if (Si < sLen)
                return (Si + 1);
            else
                return -1;
        }

        static public int IndexOfHS(string haystack, string pattern, int off)
        {
            haystack = haystack.Substring(off);
            if (pattern.Length > haystack.Length) return -1;
            if (pattern == "") return off;
            int index = HorspoolIndex(haystack, pattern, pattern.Length);
            for (int i = 0; i < pattern.Length; i++)
            {
                if (index == -1)     //因为考虑到可能返回-1的情况，出现过数组越界
                    return -1;
                if (pattern[i] != haystack[index + i])
                    return -1;
            }
            return index + off;
        }

        //BF(暴力匹配)O（m*n）
        //BF匹配算法，时间复杂度O(m*n)
        static public int BFIndex(string source, string target, int pos)
        {
            int i = pos, j = 0;
            while (i + j < source.Length && j < target.Length)
            {
                if (source[i + j] == target[j])
                {
                    j++;
                }
                else
                {
                    i++;
                    j = 0;
                }
            }
            if (j == target.Length)
            {
                return i;
            }
            else
            {
                return -1;
            }
        }
        static public int IndexOfBF(string haystack, string pattern, int off)
        {
            haystack = haystack.Substring(off);
            if (pattern.Length > haystack.Length) return -1;
            if (pattern == "") return off;
            int index = BFIndex(haystack, pattern, pattern.Length);
            for (int i = 0; i < pattern.Length; i++)
            {
                if (index == -1)     //因为考虑到可能返回-1的情况，出现过数组越界
                    return -1;
                if (pattern[i] != haystack[index + i])
                    return -1;
            }
            return index + off;
        }

    }
}
